home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11871 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: kuhub.cc.ukans.edu!anh
  2. From: anh@kuhub.cc.ukans.edu
  3. Newsgroups: comp.lang.c
  4. Subject: Re: REQUEST: Recursive functions
  5. Message-ID: <1996Mar26.185646.116671@kuhub.cc.ukans.edu>
  6. Date: 26 Mar 96 18:56:46 CST
  7. References: <4h7lft$8ql@cis.clark.edu> <3150334B.1802@willows.com> <4j72jhINNp77@keats.ugrad.cs.ubc.ca>
  8. Organization: University of Kansas Academic Computing Services
  9.  
  10. Now that I think about it, yeah, you are right.  I could find my way out 
  11. but I would not necessary visit the whole maze per se, and I could also 
  12. be wandering in circles.  Oh, well,
  13.  
  14. How about this one (2-minute's solution):
  15.  
  16. If the maze is represented as a 2d array,
  17.  
  18. Assume the walls are marked as Maze[i][j]='x'.
  19. The empty cells with Maze[i][j]='u'.
  20.  
  21. Just 'walk' thru the maze but mark the starting position with
  22. Maze[starty][startx]='s', and other positions with Maze[i][j]='w' to 
  23. indicate you have been there.  At each intersection, roll the dice and 
  24. pick a direction.  You can simply backtrack along the 'w' trail when 
  25. you run into a dead-end or into your own track, at each backtrackking step, 
  26. check for a new possible direction.  If you get back to 's' and no other 
  27. directions possible and no cheese, then no cheese. :-)
  28.  
  29. Some notes:
  30.  
  31. I would just pick a direction and keep going until I cannot go further 
  32. in the same direction.  But, before I backtrack, I check to see if I can 
  33. go in another direction.
  34.  
  35. Anh
  36.  
  37. In article <4j72jhINNp77@keats.ugrad.cs.ubc.ca>, c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) writes:
  38. > In article <1996Mar25.125041.116595@kuhub.cc.ukans.edu>,
  39. >  <anh@kuhub.cc.ukans.edu> wrote:
  40.  
  41. > False. You will visit the whole maze if it is isomorphic to a connected,
  42. > acyclic graph.  Then, the search you describe is basically a depth-first
  43. > traversal.
  44. > 
  45. > If the maze has cycles, you will end up not visiting some of the cells. You
  46. > might not even find your way out, if the starting point is in the centre, and
  47. > the rule of keeping to the right forces you to follow a wall that is surrounded
  48. > by a loop.
  49. > -- 
  50. > 
  51.